/**
 * Created With IntelliJ IDEA
 * Description:牛客网: NC145 01背包
 * <a href="https://www.nowcoder.com/practice/2820ea076d144b30806e72de5e5d4bbf?tpId=196&tqId=37561&ru=/exam/oj">...</a>
 * User: DELL
 * Data: 2023-04-26
 * Time: 15:14
 */

/**
 * 本题是动态规划典型例题(每个物品只能装入一次)
 * 假定记录物品的二维数组为 vw,且第一列为 体积,第二列为 重量
 * 状态定义: dp[i][j] : 当背包容量为 j 的时候,使用前 i 个物品装背包,可以得到的最大的重量
 * 转移方程: 一.当第i个物品的体积小于等于当前背包的体积 j 的时候 vw[i-1][0] <= j
 *          1) 将当前物品装入背包
 *          dp[i][j] = dp[i-0][j - vw[i-1][0]] + vw[i-1][1]
 *          2) 不将当前物品装入背包
 *          dp[i][j] = dp[i-1][j]
 *          因此 dp[i][j] = max(dp[i-0][j - vw[i-1][0]] + vw[i-1][1] , dp[i-1][j])
 *          二.当第i个物品的体积大于当前背包的体积 j 的时候 vw[i-1][0] > j
 *          因为该物品装不下,因此
 *          dp[i][j] = dp[i-1][j]
 * 初始值: 初始dp数组的第一行和第一列为全 0
 * 返回值: 返回数组右下角的值即可
 */
public class Solution {
    /**
     * 一般解法
     * @param v int整型 背包的体积
     * @param n int整型 物品的个数
     * @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
     * @return int整型
     */
    public int knapsack (int v, int n, int[][] vw) {
        //状态数组
        int[][] dp = new int[n+1][v+1];
        //数组默认为0,不需要初始化
        //状态转移
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= v; j++) {
                if (vw[i-1][0] <= j) {
                    dp[i][j] = Math.max(dp[i-1][j - vw[i-1][0]] + vw[i-1][1] , dp[i-1][j]);
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[n][v];
    }
    /**
     * 改进解法
     * 观察dp数组,我们每次进行状态转移的时候,只和上一行靠左的元素有关,因此这个时候我们可以进行
     * dp数组的压缩,使空间复杂度大大降低
     * 注意: 因为是和上一行靠左的元素有关,因此我们在状态转移的时候要逆向来遍历,
     * 即保存上一行原始数据
     * @param v int整型 背包的体积
     * @param n int整型 物品的个数
     * @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
     * @return int整型
     */
    public int knapsack2 (int v, int n, int[][] vw) {
        //状态数组 (压缩空间)
        int[] dp = new int[v+1];
        //数组默认为0,不需要初始化
        //状态转移
        for (int i = 1; i <= n; i++) {
            //这里需要逆向遍历
            for (int j = v; j > 0; j--) {
                if (vw[i-1][0] <= j) {
                    dp[j] = Math.max(dp[j - vw[i-1][0]] + vw[i-1][1] , dp[j]);
                }
            }
        }
        return dp[v];
    }
}